package david.java.practice.test;

import java.util.Arrays;

/**
 * @Description: 二刷
 * @Author: ZhaoDawei
 * @Date: Create in 9:55 上午 2022/4/13
 */
public class Sort {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(bubbleSort(getInput())));

        int[] i2 = getInput();
        quickSort(i2, 0, i2.length - 1);
        System.out.println(Arrays.toString(i2));
        int[] i3 = getInput();
        selectSort(i3);
        System.out.println(Arrays.toString(i3));
        int[] i4 = getInput();
        insertSort(i4);
        System.out.println(Arrays.toString(i4));

        int[] i5 = getInput();
        System.out.println("=========== merge sort ===============");
        System.out.println(Arrays.toString(mergeSort(i5, 0, i5.length - 1)));

        int[] i6 = getInput();
        heapSort2(i6);
        System.out.println("=========== heap sort ===============");
        System.out.println(Arrays.toString(i6));

        int[] i7 = getInput();
        quickSort2(i7, 0, i7.length-1);
        System.out.println("=========== quick2 sort ===============");
        System.out.println(Arrays.toString(i7));

        int[] i8 = getInput();
        System.out.println(binarySearch(i8, 5));
    }


    private static int[] getInput() {
        return new int[]{3, 1, 2, 4, 7, 5, 6, 8};
    }

    private static void swap(int[] input, int l1, int l2) {
        int t = input[l1];
        input[l1] = input[l2];
        input[l2] = t;
    }

    /**
     * 功能描述: 1: 冒泡
     *
     * @param input
     * @return:
     */
    public static int[] bubbleSort(int[] input) {
        if (input == null || input.length <= 1) {
            return input;
        }

        for (int i = 0; i < input.length; i++) {
            for (int j = i + 1; j < input.length - i; j++) {
                if (input[j] < input[j - 1]) {
                    swap(input, j, j - 1);
                }
            }
        }

        return input;
    }

    /**
     * 功能描述: 2: 快排
     *
     * @param
     * @return:
     */
    public static void quickSort(int[] input, int begin, int end) {
        if (input == null || input.length < 2) {
            return;
        }

        if (begin >= end) {
            return;
        }
        int pivot = input[begin];
        int b = begin;
        int e = end;

        while (b < e) {

            while (b < e && input[b] < pivot) {
                b++;
            }

            while (b < e && input[e] > pivot) {
                e--;
            }

            if (b < e && input[e] == input[b]) {
                b++;
            }

            if (b < e && input[b] > input[e]) {
                swap(input, b, e);
            }
        }

        if (b - 1 > begin) {
            quickSort(input, begin, b - 1);
        }
        if (e + 1 < end) {
            quickSort(input, e + 1, end);
        }
    }

    /**
     * 功能描述: 3选择排序
     *
     * @param input
     * @return:
     */
    public static void selectSort(int[] input) {
        if (input == null || input.length < 2) {
            return;
        }

        for (int i = 0; i < input.length; i++) {
            int min = i;
            for (int j = i; j < input.length; j++) {
                if (input[j] < input[min]) {
                    min = j;
                }
            }
            swap(input, i, min);
        }
    }

    /**
     * 功能描述: 插入排序
     *
     * @param input
     * @return:
     */
    public static void insertSort(int[] input) {
        if (input == null || input.length < 2) {
            return;
        }
        for (int i = 0; i < input.length; i++) {
            for (int j = i; j > 0; j--) {
                if (input[j] < input[j - 1]) {
                    swap(input, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static int[] mergeSort(int[] input, int begin, int end) {
        if (input == null) {
            return input;
        }

        if (begin == end) {
            return new int[]{input[begin]};
        }

        int mid = (begin + end) / 2;

        int[] left = mergeSort(input, begin, mid);
        int[] right = mergeSort(input, mid + 1, end);
        int[] merge = new int[left.length + right.length];

        int m = 0, l = 0, r = 0;
        while (l < left.length && r < right.length) {
            merge[m++] = left[l] < right[r] ? left[l++] : right[r++];
        }

        while (l < left.length) {
            merge[m++] = left[l++];
        }

        while (r < right.length) {
            merge[m++] = right[r++];
        }


        return merge;


    }


    public static void heapSort2(int[] input) {
        if (input == null || input.length < 2) {
            return;
        }
        for (int k = input.length - 1; k > 0; k--) {
            build2(input, k);
            swap(input, 0, k);
        }

    }

    private static void build2(int[] input, int k) {
        for (int i = input.length / 2 - 1; i >= 0; i--) {
            adjust2(input, i, k);
        }
    }


    private static void adjust2(int[] input, int i, int k) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l > k) {
            return;
        }

        int maxChild = r > k ? l : input[l] > input[r] ? l : r;

        if (input[i] < input[maxChild]) {
            swap(input, i, maxChild);
            adjust2(input, maxChild, k);
        }
    }


    public static void quickSort2(int[] input, int begin, int end) {
        if (input == null) {
            return;
        }
        if (begin >= end) {
            return;
        }

        int pivot = input[begin];
        int b = begin;
        int e = end;

        while (b < e) {
            while (b < e && input[b] < pivot) {
                b++;
            }
            while (b < e && input[e] > pivot) {
                e--;
            }
            if (b < e && input[e] == input[b]) {
                b++;
            }
            if (b < e && input[b] > input[e]) {
                swap(input, b, e);
            }
        }

        if (begin < b -1) {
            quickSort(input, begin, b - 1);
        } 
        if (b + 1 < end) {
            quickSort(input, b + 1, end);
        }
    }


    public static int binarySearch(int[] input, int target) {
        if (input == null || input.length == 0) {
            return -1;
        }
        Arrays.sort(input);
        int b = 0, e = input.length - 1;
        int mid = (b + e) / 2;

        while (b <= e) {
            if (target > input[mid]) {
                b = mid + 1;
                mid = (b + e) / 2;
            }
            if (target < input[mid]){
                e = mid -1;
                mid = (b + e) / 2;
            }
            if (target == input[mid]) {
                return mid;
            }

        }

        return -1;

    }

}
